package Linked_List;

import LeetCode_206.ListNode;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/27 21:22
 */


public class MyLinkedList {
    static class Node {
        public int val;
        private Node next;
        private Node prev;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;
    private Node last;
    private int size;

    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        node.prev = null;
        if (size > 0) {
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        } else {
            this.head = this.last = node;
            node.next = null;
        }
        size++;
    }

    //尾插法
    public void addLast(int data) {
        Node node = new Node(data);
        node.next = null;
        if (size > 0) {
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        } else {
            this.head = this.last = node;
            node.prev = null;
        }
        size++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index, int data) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }
        //size == 0 直接加
        if (size == 0) {
            addLast(data);
            return true;
        }
        //size == 1 为了通常情况排除
        if (size == 1) {
            if (index == 0) {
                addFirst(data);
            } else {
                addLast(data);
            }
            return true;
        }
        //排除首尾
        if (index == 0) {
            addFirst(data);
            return true;
        } else if (index == size) {
            addLast(data);
            return true;
        }
        // size  >1 && index > 0 && index < size
        Node node = new Node(data);

        Node prev = this.head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        Node cur = prev.next;

        prev.next = node;
        cur.prev = node;
        node.next = cur;
        node.prev = prev;
        size++;
        return true;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        Node temp = this.head;
        while (temp != null) {
            if (temp.val == key) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (!contains(key)) {
            return;
        }
        Node cur = head;
        while (cur != null) {
            if (cur.val == key) {
                //判断当前是不是头节点
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    }
                } else {
                    //中间和尾巴的情况
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = last.prev;
                    }
                }
                size--;
                cur = cur.next;
            } else {
                cur = cur.next;
            }
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (!contains(key)) {
            return;
        }
        Node cur = head;
        while (cur != null) {
            if (cur.val == key) {
                //判断当前是不是头节点
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    }
                } else {
                    //中间和尾巴的情况
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = last.prev;
                    }
                }
                size--;
                cur = cur.next;
            } else {
                cur = cur.next;
            }
        }
    }

    //得到单链表的长度
    public int size() {
        return size;
    }

    public void display() {
        Node node = head;
        for (int i = 0; i < size; i++) {
            System.out.print("val = " + node.val);
            node = node.next;
        }
    }

    public void clear() {
        this.head = this.last = null;
        this.size = 0;
    }
}
